#ifndef NORMALLIST_H_INCLUDED
#define NORMALLIST_H_INCLUDED
#include <unistd.h>
#include <iostream>

template<typename Object>
class NormalList{
    struct Node{
        Object ob;
        Node * next;
        Node(const Object & x , Node * n ):ob(x),next(n){}
        Node(){next = NULL;}
    };
public:
    NormalList(){

        head = new Node();
        tail = new Node();

        thesize = 0;
        head->next = tail;
        tail->next = NULL;
        before_tail = head;
    }

    void pushtolist(const Object & x)
    {
        thesize++;
        std::cout << "push " << x << std::endl;
        Node * newnode = new Node(x,before_tail->next);
        before_tail->next = newnode;
        before_tail = before_tail->next;

    }


    void printall()
    {
        int pos = 0;
        Node * np = head;
        while(pos != thesize)
        {
            pos++;
            np = np->next;
            std::cout <<"x= " << np->ob << std::endl;

        }

    }


    Node * findkth(int k)
    {
        if(k == -1)
        {
            return head;
        }

        if(thesize == 0)
        {
            std::cout << "empty" << std::endl;
            return NULL;
        }

        int pos = 0;
        Node * np = head->next;
        while(pos != k && np != tail)
        {
            pos++;
            np = np->next;

        }
        return np;

    }

    const Object & getkthvalue(int k)
    {
        Node * np = findkth(k);
        return np->ob;
    }

    void swapthem(int p1, int p2)
    {


        if(thesize < 2 || p1 == p2 || p1 > p2)
        {
            std::cout << "fuck !!" << std::endl;
            return;
        }
        Node * np1 = findkth(p1);

        Node * np2 = findkth(p2);

        /*before_tail need to change*/
        if(before_tail == np2)
        {
            before_tail = np1;
        }

        Node * prev_np1 = findkth(p1 - 1);

        prev_np1->next = np2;
        np1->next = np2->next;
        np2->next = np1;



    }


private:
    int thesize;
    Node * head;
    Node * tail;
    Node * before_tail;

};




#endif // NORMALLIST_H_INCLUDED
